package algorithms.leecode;

public class Au64 {
    public static void main(String[] args) {
        System.err.println(new Au64().minPathSum(
                new int[][]{
                        {1,2,3},
                        {4,5,6}
                }
        ));
    }
    public int minPathSum(int[][] grid) {
        int len = grid.length;
        int len1 = grid[0].length;
        int[] zc = new int[len];
        int[] zf = null;
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len; j++) {
                int x = len1 - i - 1;
                int y = len - j - 1;
                if (j == 0) {
                    if (i == 0) {
                        zc[j] = grid[y][x];
                    } else {
                        zc[j] = zf[j] + grid[y][x];
                    }
                } else {
                    zc[j] = Math.min(zc[j - 1],zf == null ? Integer.MAX_VALUE : zf[j]) + grid[y][x];
                }
            }
            zf = zc;
            zc = new int[len];
        }
        return zf[len - 1];
    }
}
